home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-01
/
bfsorts.zip
/
MLSORT.C
< prev
next >
Wrap
C/C++ Source or Header
|
1990-12-26
|
5KB
|
198 lines
/***********************************************************************/
/* SORT(): Non-Recursive Merge List Sort function. */
/* See the function declaration for calling information. */
/* Function is by Bruce Feist; please contact me on CompuServe with */
/* a message on BPROGB, MACDEV, or EASYPLEX if you have any */
/* questions or problems. */
/* You can also reach me at the Enlightened Board, at (703) 370-9528, */
/* N/8/1 */
/* Feel free to make use of this code in your own programs. */
/***********************************************************************/
/* Merge/List sort. Fast, but uses even more space than msort. */
/* Like merge sort, but takes advantage of any preexisting ordered sublists. */
#include <alloc.h>
#include <mem.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include "sort.h"
#define ENDLIST -1
#define VERBOSE (0)
static char *base;
static unsigned int nelem, width;
static int (*compare) (void *, void *);
static int merge (int left, int right);
static void show_lists (int *lists, int nlists);
static void show_list (int list);
static int *next; /* array: which element comes after this one? */
int
mlsort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
int *lists; /* array of pointers to sorted sublists */
unsigned int nlists, list_num;
int elem_num, temp_num;
char *temp_base;
int workspace_size;
void *workspace; /* contains lists or temp_base, depending on when */
base = pbase;
nelem = pnelem;
width = pwidth;
compare = pcompare;
#if VERBOSE
printf ("MLsort (%p, %d, %d, %p).\n", pbase, pnelem, pwidth, pcompare);
#endif
workspace_size = nelem * max (sizeof (*lists) + sizeof (*next), width);
workspace = malloc (workspace_size);
if (workspace == NULL)
return S_NOMEM;
temp_base = workspace;
lists = workspace; /* it's never used concurrently with temp_base! */
next = malloc (nelem * sizeof (*next));
if (next == NULL)
return S_NOMEM;
lists[0] = 0;
nlists = 1;
for (elem_num = 1;
elem_num < nelem;
elem_num++)
{
if (compare(base + (elem_num - 1) * width,
base + elem_num * width) > 0)
{
next [elem_num - 1] = ENDLIST;
lists [nlists] = elem_num;
nlists++;
}
else
{
next [elem_num - 1] = elem_num;
}
} /* end for */
next [nelem - 1] = ENDLIST;
while (nlists > 1)
{ /* Merge pairs of lists */
for (list_num = 0;
list_num < (nlists - 1);
list_num++, nlists--)
{
#if VERBOSE
show_lists (lists, nlists);
printf ("\nMerging list %d with list %d:\n", list_num, list_num + 1);
#endif
lists[list_num] = merge (lists[list_num], lists[list_num + 1]);
lists[list_num + 1] = lists[nlists - 1];
} /* end for */
} /* end while */
#if VERBOSE
show_lists (lists, nlists);
#endif
/* move everything to where it belongs. */
for (elem_num = 0, temp_num = lists[0];
elem_num < nelem;
elem_num++, temp_num = next [temp_num])
{
memcpy (temp_base + width * elem_num, base + width * temp_num, width);
}
memcpy (base, temp_base, width * nelem);
return S_OK;
} /* end msort */
int
merge (int left, int right)
{
int first, last;
char *left_ptr, *right_ptr;
left_ptr = base + left * width;
right_ptr = base + right * width;
if (compare (left_ptr, right_ptr) > 0)
{
first = last = right;
right = next [right];
right_ptr = base + right * width;
}
else
{
first = last = left;
left = next [left];
left_ptr = base + left * width;
}
while (left != ENDLIST && right != ENDLIST)
{
if (compare (left_ptr, right_ptr) > 0)
{
/* right is smaller; use it */
next [last] = right;
last = right;
right = next [right];
right_ptr = base + right * width;
}
else
{
/* left is smaller; use it */
next [last] = left;
last = left;
left = next [left];
left_ptr = base + left * width;
}
}
next [last] = (left == ENDLIST) ? right : left;
return first;
} /* end merge */
void
show_lists (int *lists, int nlists)
{
int list;
for (list = 0;
list < nlists;
list++)
{
printf ("List # %d at ", list);
show_list (lists [list]);
} /* end for */
} /* end show_lists */
#pragma warn -use
void
show_list (int list)
{
int node;
printf ("%d: ", list);
for (node = list;
node != ENDLIST;
node = next [node])
{
printf ("# %d: %.4lf, ", node, *((double *) (base + node * width)));
}
printf ("\n");
} /* end show */